#include <vector>

using namespace std;


class Solution {
public:
    /**
     * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个
     * 元素均出现三次。找出那个只出现了一次的元素。
     * 注意：不使用额外空间 (位运算可以做到这点)
     * 
     * 解法：依次确定每个二进制位
     * 对于第 i 个二进制位，非答案的数字该位总和为 3 的倍数
     */
    int singleNumber(vector<int>& nums) {  // O(n log C) O(1), C is 2^32
        int res = 0;
        for (int i=0; i<32; ++i) {  // 32 bits for integers
            int sum = 0;
            for (int n : nums) sum += ((n >> i) & 1);  // 取出末位
            if (sum % 3) res |= (1 << i);  // 答案的 bit
        }
        return res;
    }
};
